Có thể chứng minh rằng khoảng cách (tính theo số cung) từ đỉnh phát đến đỉnh thu tăng lên ít nhất 1 sau mỗi lần tăng luồng bằng luồng ngăn chặn nên chỉ cần tìm không quá n − 1 {\displaystyle n-1} luồng ngăn chặn, trong đó n {\displaystyle n} là số đỉnh của đồ thị. Có thể xây dựng đồ thị tầng G L {\displaystyle G_{L}} bằng tìm kiếm theo chiều rộng trong thời gian O ( E ) {\displaystyle O(E)} và có thể tìm luồng ngăn chặn trong thời gian O ( V E ) {\displaystyle O(VE)} . Do đó thời gian chạy của thuật toán Dinitz là O ( V 2 E ) {\displaystyle O(V^{2}E)} .

Bằng cách sử dụng cấu trúc dữ liệu cây động, có thể giảm thời gian tìm mỗi luồng ngăn chặn xuống còn O ( E log ⁡ V ) {\displaystyle O(E\log V)} và do đó giảm thời gian chạy của thuật toán Dinitz xuống O ( V E log ⁡ V ) {\displaystyle O(VE\log V)} .

Trường hợp đặc biệt

Trong mạng với khả năng thông qua đơn vị, thời gian chạy của thuật toán nhanh hơn rất nhiều so với trường hợp tổng quát. Có thể tìm mỗi luồng ngăn chặn trong thời gian O ( E ) {\displaystyle O(E)} , và có thể chứng minh rằng số lần tìm luồng ngăn chặn là không quá số nhỏ hơn giữa O ( E ) {\displaystyle O({\sqrt {E}})} và O ( V 2 / 3 ) {\displaystyle O(V^{2/3})} . Do đó thuật toán chạy trong thời gian O ( min ( V 2 / 3 , E 1 / 2 ) E ) {\displaystyle O(\min(V^{2/3},E^{1/2})E)} .

Trong mạng lưới xây dựng từ bài toán ghép cặp trên đồ thị hai phía, số lần tìm luồng ngăn chặn là O ( V ) {\displaystyle O({\sqrt {V}})} , nên thời gian chạy là không quá O ( V E ) {\displaystyle O({\sqrt {V}}E)} . Thuật toán này còn được biết đến là thuật toán Hopcroft–Karp. Tổng quát hơn, chặn trên cho thời gian chạy này đúng cho mọi mạng đơn vị — mạng trong đó mỗi đỉnh, ngoại trừ đỉnh phát và đỉnh thu, hoặc có đúng một cung vào với khả năng thông qua bằng một, hoặc đúng một cung ra với khả năng thông qua bằng một và tất cả các cung khác có khả năng thông qua là số nguyên tùy ý.[2]